ჰეშირება - ცხრილის
გაორმაგება (Table Doubling).
კარპ-რაბინის (Karp-Rabin)
ალგორითმი
მარიამ გობრონიძე
Load Factor (ტვირთვის კოეფიციენტი ) ჰეშ-ცხრილის ეფექტურობის გასაზომად გამოიყენება.
იგი განისაზღვრება როგორც:
Load Factor=n/m
სადაც:
● n – ჰეშ-ცხრილში შენახული ელემენტების რაოდენობა (keys count)
● m – ჰეშ-ცხრილის ბაკეტების რაოდენობა (buckets count)
Load Factor (ტვირთვის კოეფიციენტი)
ჰეშირებაში
Load Factor-ის მნიშვნელობა და გავლენა
თუ Load Factor ძალიან მცირეა (< 0.5) → ჰეშ-ცხრილში ბევრი ცარიელი ბაკეტია,
მეხსიერების ფუჭი ხარჯვა ხდება.
თუ Load Factor ძალიან დიდია (> 1.0) → ბევრი ელემენტი ერთსა და იმავე
ბაკეტში ხვდება, კოლიზიები იზრდება და ძიების სიჩქარე მცირდება.
იდეალური Load Factor ჩვეულებრივ 0.7-ის ფარგლებშია , რაც ბალანსს ქმნის
მეხსიერებასა და ძიების სიჩქარეს შორის.
როდესაც Load Factor იზრდება – Rehashing
(გადახარისხება)
თუ Load Factor ზედმეტად დიდი ხდება , შეიძლება Rehashing მოვახდინოთ:
1. ვქმნით ახალ, უფრო დიდ ჰეშ-ცხრილს (მაგ., ორჯერ უფრო მეტ ბაკეტს ვამატებთ).
2. ძველი ცხრილიდან ყველა გასაღებს თავიდან ვინახავთ ახალ ცხრილში.
3. ეს ამცირებს კოლიზიებს და ზრდის ჰეშ-ცხრილის ეფექტურობას.
დავუშვათ, გვაქვს ჰეშ-ცხრილი m = 5 ბაკეტით და მასში 10 გასაღებია:
Load Factor=10/5=2
ეს ნიშნავს, რომ ერთ ბაკეტში საშუალოდ 2 ელემენტია , რაც კოლიზიებს ზრდის.
თუ ბაკეტების რაოდენობას გავაორმაგებთ (rehashing), ვიღებთ:
Load Factor=10/10=1
კოლიზიები მცირდება, ძიება სწრაფდება.
👉 Load Factor-ის კონტროლი აუცილებელია ჰეშ-ცხრილის ეფექტურად მუშაობისთვის !
მაგალითი
რეჰეშირება
ეს ფუნქცია გამოთვლის ჰეშ-ცხრილის ტვირთვის კოეფიციენტს . თუ ტვირთვის
კოეფიციენტი მაღალია (მაგ. 0.5-ზე მეტი), ჰეშ-ცხრილი საჭიროებს rehashing-ს.
ეს მნიშვნელობა საყურადღებოა, რადგან ტვირთვის კოეფიციენტი გვეუბნება, როდის
უნდა მოხდეს ცხრილის ზომის გაორმაგება.
rehashing-ის
ფუნქცია
აორმაგებს
ცხრილის ზომას
და ყველა
ელემენტი ახალ
უჯრაში გადააქვს.
ამისთვის
insertItem
მეთოდი ხელახლა
გამოიძახება.
რეჰეშირება
რეჰეშირება
აქ, როგორც კი ტვირთვის კოეფიციენტი 0.5-ს
აღემატება, ავტომატურად ხდება rehashing.
შემდეგ, ელემენტი გადანაწილდება შესაბამის
უჯრებში.
კარპ-რაბინის (Karp-Rabin)
ალგორითმი
კომპიუტერულ მეცნიერებაში Rabin–Karp-ის ალგორითმი (ან
Karp–Rabin-ის ალგორითმი) არის სტრიქონების საძიებო
ალგორითმი, რომელიც შექმნეს რიჩარდ კარპმა და მაიკლ რაბინმა
(1987 წელს).
ალგორითმი იყენებს ჰეშირებას, რათა იპოვოს ზუსტი შესაბამისობა
ნიმუშის (pattern) სტრიქონსა და ტექსტს შორის.
განსხვავებით სტრიქონების ძიების უმარტივესი ალგორითმისგან
(Naive string matching algorithm), კარპ რაბინის ალგორითმი საწყის
ეტაპზე არ ამოწმებს ტექსტის თითოეულ სიმბოლოს, არამედ
წინასწარ ფილტრავს იმ სიმბოლოებს, რომლებიც ნიმუშს არ
ემთხვევა, ხოლო შედარებას მხოლოდ შესაბამის პოზიციებზე
ასრულებს.
მაგალითი
მოცემულია ტექსტი T[0...n-1] და ნიმუში P[0...m-1]. შექმენით ფუნქცია search(char
P[], char T[]), რომელიც რაბინ–კარპის ალგორითმის გამოყენებით ბეჭდავს ყველა იმ
პოზიციას, სადაც P[] გვხვდება T[]-ში. შეგიძლიათ ჩათვალოთ, რომ n > m.
მაგალითები :
რაბინ –კარპის ალგორითმი
სტრიქონების ძებნის ნაივურ ალგორითმში , ტექსტის ყველა m ზომის ქვეწინადადებას ვამოწმებთ
ნიმუშთან თანხვედრაზე, თითოეულ მათგანს ცალკე ვადარებთ ნიმუშს.
რაბინ–კარპის ალგორითმიც ასევე ამოწმებს ყველა ქვეწინადადებას, თუმცა ნაივური ალგორითმისგან
განსხვავებით , ის პირველ ეტაპზე მხოლოდ ნიმუშისა და ტექსტის ქვეწინადადების ჰეშ-მნიშვნელობებს
ადარებს. მხოლოდ მაშინ, როდესაც ჰეშ-მნიშვნელობები ემთხვევა, იწყება ნამდვილი სიმბოლოების
შედარება.
ამგვარად, რაბინ–კარპის ალგორითმი ჰეშ-მნიშვნელობებს ითვლის შემდეგი ობიექტებისთვის:
1. ნიმუში (Pattern) თავად
2. ტექსტის ყველა ქვეწინადადება , რომლის სიგრძე ტოლია m-ის (ნიმუშის ზომის)
როგორ ითვლება ჰეშ-მნიშვნელობა
რაბინ –კარპის ალგორითმში ?
ჰეშ-მნიშვნელობა გამოიყენება, რათა ეფექტურად შევამოწმოთ პოტენციური
დამთხვევები ნიმუშსა და ტექსტის ქვეწინადადებებს შორის.
ჰეშ-მნიშვნელობა გამოითვლება მოძრავი ჰეშის (Rolling Hash) ფუნქციის
გამოყენებით, რომელიც საშუალებას გვაძლევს ახალი ქვეწინადადების ჰეშ-
მნიშვნელობა სწრაფად განვაახლოთ:
● ჰეშ-მნიშვნელობიდან ეფექტურად მოიხსნება წინა ქვეწინადიდების სიმბოლოს
გავლენა
● დაემატება ახალი სიმბოლოს გავლენის
ეს მეთოდი საშუალებას იძლევა, ნიმუში ტექსტზე ეტაპობრივად
გადავაადგილოთ და თითოეული ქვეწინადების ჰეშ-მნიშვნელობა
დავადგინოთ, ისე რომ არ დაგვჭირდეს მისი გამოთვლა “ნულიდან”.
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ნაბიჯი 1: შესაფერისი ბაზისა და მოდულის არჩევა
● აირჩიეთ მარტივი რიცხვი p მოდულად, რათა თავიდან აიცილოთ გადავსების
პრობლემები და უზრუნველყოთ ჰეშ-მნიშვნელობების კარგი გადანაწილება.
● აირჩიეთ ბაზა b (სასურველია მარტივი რიცხვი), რომელიც ხშირად ემთხვევა
სიმბოლოების სიმრავლის ზომას (მაგ., 256 ASCII სიმბოლოებისთვის ).
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ნაბიჯი 2: ჰეშ-მნიშვნელობის ინიციალიზაცია
● საწყისი ჰეშ-მნიშვნელობა hash დააყენეთ 0-ზე.
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ნაბიჯი 3: ნიმუშის საწყისი ჰეშ-მნიშვნელობის გამოთვლა
● გაიარეთ ნიმუშის თითოეული სიმბოლო მარცხნიდან მარჯვნივ.
● თითოეული c სიმბოლოსთვის i პოზიციაზე გამოითვალეთ მისი წვლილი ჰეშ-
მნიშვნელობაში:
● საბოლოოდ მიიღებთ ნიმუშის სრულ ჰეშ-მნიშვნელობას .
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ნაბიჯი 4: ნიმუშის გადანაცვლება ტექსტში
● ჯერ გამოთვალეთ ჰეშ-მნიშვნელობა ტექსტის პირველი ქვეწინადადებისთვის , რომელიც
ნიმუშის სიგრძის ტოლია.
ნაბიჯი 5: ჰეშ-მნიშვნელობის განახლება ყოველი ახალი ქვეწინადისთვის
● ნიმუშის ერთი პოზიციით მარჯვნივ გადატანისას :
○ წაშალეთ მარცხენა (ძველი) სიმბოლოს მნიშვნელობა ჰეშ-მნიშვნელობიდან.
○ დაამატეთ ახალი სიმბოლოს მნიშვნელობა მარჯვნიდან.
● განახლების ფორმულა:
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ჰეშ-მნიშვნელობის გამოთვლის
პროცედურა რაბინ–კარპის ალგორითმში:
ნაბიჯი 6: ჰეშ-მნიშვნელობების შედარება
● როდესაც ქვეწინადადების ჰეშ-მნიშვნელობა ემთხვევა ნიმუშის ჰეშს, ეს ნიშნავს
პოტენციურ დამთხვევას .
● თუმცა, ჰეშ-კოლიზიების (შემთხვევითი დამთხვევების) გამო საჭიროა სიმბოლოების
პირდაპირი შედარება , რათა დავრწმუნდეთ, რომ ნიმუში რეალურად ემთხვევა ტექსტის
შესაბამის ნაწილს.
ილუსტრაცია
ფორმულები Rabin-Karp ალგორითმისთვის
Rabin-Karp იყენებს პოლინომური ჰეშირებას , რომელიც გამოითვლება
შემდეგი ფორმულით:
სადაც:
● S — ტექსტის ქვეწინადადება ან ნიმუში.
● d — ალფავიტის ზომა (ASCII-სთვის d=256).
● q — მარტივი რიცხვი, რომელიც გამოიყენება ჰეშირებისთვის (უმჯობესია, რათა
თავიდან ავირიდოთ კოლიზიები).
● M — ნიმუშის სიგრძე.
● ord(S[i]) — სიმბოლოს ASCII ან Unicode მნიშვნელობა.
ნიმუში: "ABC"
● d=256, q=101
H("ABC")=(ord("A")⋅256^2+ord("B")⋅256^1+ord("C")⋅256^0)mod 101
მაგალითი
მოძრავი ჰეშ-ფუნქცია (Rolling Hash) ახალი
ქვეწინადისთვის
რადგან ტექსტში ძიებისას საჭიროა ნიმუშის გადაადგილება (Slide), ყოველი ახალი
ქვეწინადის ჰეში გამოითვლება წინა ჰეშისგან :
სადაც:
● H(Ti:i+M)— მიმდინარე ქვეწინადადების ჰეში.
● H(Ti+1:i+M+1)— ახალი ქვეწინადადების ჰეში.
● ord(T[i])— წასაშლელი სიმბოლოს ASCII მნიშვნელობა.
● ord(T[i+M])— ახალი დამატებული სიმბოლოს ASCII მნიშვნელობა.
● h=d^(M−1) — წინასწარ გამოთვლილი მნიშვნელობა, რომელიც საჭიროა ჰეშის
განახლებისთვის.
ნაბიჯები
საწყის ეტაპზე გამოთვალეთ ნიმუშის ჰეშ-მნიშვნელობა .
დაიწყეთ ტექსტში გადაადგილება მარცხნიდან მარჯვნივ :
● გამოითვალეთ მიმდინარე ქვეწინადადების (რომლის სიგრძე ტოლია m-ის) ჰეშ-
მნიშვნელობა.
● თუ ნიმუშისა და მიმდინარე ქვეწინადადების ჰეშ-მნიშვნელობები ერთმანეთს
ემთხვევა, შეამოწმეთ, მართლაც ემთხვევა თუ არა ეს ქვეწინადადება ნიმუშს.
● თუ ქვეწინადადება ნიმუშს ემთხვევა, შეინახეთ მისი საწყისი ინდექსი როგორც სწორი
პასუხი.
● წინააღმდეგ შემთხვევაში, განაგრძეთ შემდგომი ქვეწინადადების განხილვა.
დააბრუნეთ ყველა ნაპოვნი საწყისი ინდექსი საბოლოო პასუხად .
ცვლადების ინიციალიზაცია :
● d = 256 – სიმბოლოების ალფაბეტის ზომა (ASCII-სთვის 256).
● m – შაბლონის (pattern-ის) სიგრძე.
● n – ტექსტის (txt-ის) სიგრძე.
● hash_pattern – შაბლონის ჰეში.
● hash_text – ტექსტის მიმდინარე ფანჯრის ჰეში.
● h – მნიშვნელობა, რომელიც გამოიყენება ჰეშის ხელახლა დასათვლელად.
პრაქტიკული იმპლემენტაცია
პირველი ჰეშის გამოთვლა
● გამოითვლება h = (d^(M-1)) % prime_modulus – ეს მნიშვნელობა საჭიროა მომდევნო ჰეშის
სწრაფად გამოსათვლელად.
● გამოითვლება საწყისი ჰეშები hash_pattern (შაბლონისთვის) და hash_text (ტექსტის პირველი
M სიგრძის ქვეწინადადებისთვის).
ნიმუშისა და ტექსტის პირველი ქვეწინადადების ჰეშ მნიშვნელობების დათვლა:
● ord(pattern[i]) - უზრუნველყოფს სიმბოლო i-ის კოდის მიღებას.
● გამოთვლა ხდება d და prime_modulus-ის გამოყენებით.
შემდეგი კოდი იწყებს ნიმუშის გადატანას ტექსტში, შეამოწმებს
ყველა შესაძლო ქვეწინადადებას ტექსტში, რომლის სიგრძეც m-ის
ტოლია (ნიმუშის სიგრძე).
თუ ჰეშ-მნიშვნელობები ემთხვევა, მაშინ იწყება თითოეული
სიმბოლოს შედარება:
● თუ რომელიმე სიმბოლო არ ემთხვევა, წყდება ციკლი და
გადადის შემდეგ ქვეწინადადებაზე.
● თუ ყველა სიმბოლო ემთხვევა, მაშინ ნიმუში ნაპოვნია, და
დავაბრუნებთ პატერნის ინდექსს.
როდესაც ნიმუშის (pattern) ერთ ქვეწინადადებაზე დასრულდება შედარება,
საჭიროა ახალი ჰეშ-მნიშვნელობის გამოთვლა შემდეგი
ქვეწინადადებისათვის.
● უნდა მოიხსნას პირველი სიმბოლო და ახალი სიმბოლო (ტექსტის შემდეგი
სიმბოლო) დაემატოს.
დროითი სირთულე
Rabin-Karp-ის ალგორითმის საშუალო და საუკეთესო შემთხვევებში გაშვების
დროის სირთულე არის O(n + m), ხოლო უარესი შემთხვევისთვის – O(nm).
უარესი შემთხვევა მაშინ ხდება, როდესაც ტექსტისა და ნიმუშის ყველა
სიმბოლო ერთნაირია, რის შედეგადაც ტექსტის ყველა ქვეწინადადების ჰეშის
მნიშვნელობა ემთხვევა ნიმუშის ჰეშის მნიშვნელობას.
დამატებითი მეხსიერება : O(1)
Rabin-Karp-ის ალგორითმის შეზღუდვები
ცრუ დამთხვევა (Spurious Hit):
ცრუ დამთხვევა მაშინ ხდება, როდესაც ნიმუშისა და ტექსტის გარკვეული ფანჯრის
ჰეშის მნიშვნელობები ერთმანეთს ემთხვევა, მაგრამ აღნიშნული ფანჯარა
სინამდვილეში ნიმუშს არ წარმოადგენს.
ცრუ დამთხვევები ზრდის ალგორითმის დროის სირთულეს. მათ
მინიმიზაციისთვის ვიყენებთ ეფექტურ ჰეშ-ფუნქციას, რომელიც მნიშვნელოვნად
ამცირებს ცრუ დამთხვევების რაოდენობას.
გმადლობთ ყურადღებისთვის!
